package com.benyi.util;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 本算法缺点：不能连除, 如：  100/10/5/2 的结果不正确， 必须加 括号 ((100/10)/5)/2 才能得到正确值
 * @author admin
 *
 */
public class Calculator {  
	  
    private static final char[] op = {'+','-','*','/','(',')'};  
    private static final String[] strOp = {"+","-","*","/","(",")"};  

    public static boolean isDigit(char c){  
        if(c>='0'&&c<='9'){  
            return true;  
        }  
        return false;  
    }  
    public static boolean isOp(char c){  
        for(int i=0;i<op.length;i++){  
            if(op[i]==c){  
                return true;  
            }  
        }  
        return false;  
    }  
    
    private static boolean isOp(String s){  
        for(int i=0;i<strOp.length;i++){  
            if(strOp[i].equals(s)){  
                return true;  
            }  
        }  
        return false;  
    }  
    /** 
     * 处理输入的计算式 
     * @param str 
     * @return 
     */  
    private static List<String> work(String str){  
        List<String> list = new ArrayList<String>();  
        char c;  
        StringBuilder sb = new StringBuilder();  
        for(int i=0;i<str.length();i++){  
            c = str.charAt(i);  
            if(isDigit(c)){  
                sb.append(c);  
                  
            }  
            if(isOp(c)){  
                if(sb.toString().length()>0){  
                    list.add(sb.toString());  
                    sb.delete(0, sb.toString().length());  
                }  
                list.add(c+"");  
            }  
        }  
        if(sb.toString().length()>0){  
            list.add(sb.toString());  
            sb.delete(0, sb.toString().length());  
        }  
        return list;  
    }  
   
    /** 
     * 中缀表达式转化为后缀表达式 
     * 1,遇到数字输出 
     * 2,遇到高优先级的全部出栈 
     * 3,最后全部出栈 
     */  
    private static List<String> infixToPostfix(List<String> list){  
        List<String> postfixlist = new ArrayList<String>();//存放后缀表达式  
        Stack<String> stack = new Stack<String>();//暂存操作符  

        for(int i=0;i<list.size();i++){  
            String s = list.get(i);  
            if(s.equals("(")){  
                stack.push(s);  
            }else 
            if(s.equals("*")||s.equals("/")){  
                stack.push(s);  
            }else 
            if(s.equals("+")||s.equals("-")){  
            	dealRight(s,stack,postfixlist); 
            }else 
            if(s.equals(")")){  
            	dealRightKuhao(stack,postfixlist); 
            }else{  
            	postfixlist.add(s);  
            }  
            if(i==list.size()-1){  
                while(!stack.empty()){  
                	postfixlist.add(stack.pop());  
                }  
            }  
        }  
        return postfixlist;  
    }  
    
    private static void dealRightKuhao(Stack<String> stack,List<String> postfixlist){
    	while(!(stack.peek().equals("("))){  
        	postfixlist.add(stack.pop());  
        }  
        stack.pop();  
    }  
    
    private static void dealRight(String s,Stack<String> stack,List<String> postfixlist){
    	if(!stack.empty()){  
            while(!(stack.peek().equals("("))){  
            	postfixlist.add(stack.pop());  
                if(stack.empty()){  
                    break;  
                }  
            }  
            stack.push(s);  
        }else{  
            stack.push(s);  
        }  
    }
    
    /** 
     * 后缀表达式计算 
     */  
    private static int doCal(List<String> list){  
        Stack<Integer> stack = new Stack<Integer>();  
        for(int i=0;i<list.size();i++){  
            String s = list.get(i);  
            int t=0;  
            if(!isOp(s)){  
                t = Integer.parseInt(s);  
                stack.push(t);  
            }else{  
                if(s.equals("+")){  
                    int a1 = stack.pop();  
                    int a2 = stack.pop();  
                    int v = a2+a1;  
                    stack.push(v);  
                }else if(s.equals("-")){  
                    int a1 = stack.pop();  
                    int a2 = stack.pop();  
                    int v = a2-a1;  
                    stack.push(v);  
                }else if(s.equals("*")){  
                    int a1 = stack.pop();  
                    int a2 = stack.pop();  
                    int v = a2*a1;  
                    stack.push(v);  
                }else if(s.equals("/")){  
                    int a1 = stack.pop();  
                    int a2 = stack.pop();  
                    int v = a2/a1;  
                    stack.push(v);  
                }  
            }  
        }  
        return stack.pop();  
    }  
    
    public static int cal(String exp){
    	System.out.println(exp);
    	List<String> list = work(exp);
    	System.out.println(list);
    	List<String> list2 = infixToPostfix(list);
    	System.out.println(list2);
    	int v=doCal(list2);
    	return v;
    }
    
    public static void main(String []args){
    	long t=System.currentTimeMillis();
    	String exp="64/8/4/2";
    	int i=0;
    	int v=0;
    	int n=1;//1000000;
    	while(i<n){
    		v=cal(exp);
    		i++;
    	}
    	System.out.println("="+v+"\t"+(System.currentTimeMillis()-t)); 
    }
}  
